package test;

public class KnapsackProblem {
	public static void main(String[] args){
		int[][] arr = {{1, 1, 1},{2, 6, 2},{3, 18, 5},{4, 22, 6}, {5, 28, 7}};
		int[][] re2 = knapsack(arr, 11);
		
		int[][] array = {{1, 2, 3},{2, 3, 4},{3, 3, 2},{4, 1, 2}, {5, 6, 7},{6, 3, 5},{7, 5, 6}};
		int[][] re = knapsack(array, 14);
		for(int i = 0; i < re.length; i++){
			for(int j = 0; j < re[0].length; j++){
				System.out.print(re[i][j] + "\t");
					
			}
			System.out.println();
		}
		
	}
	
	public static int[][] knapsack(int[][] arr, int weight){
		int[][] result = new int[arr.length + 1][weight + 1];
		for(int i = 0; i <= weight; i++){
			result[0][i] = 0;
		}
		for(int i = 1; i <= arr.length; i++){
			for(int j = 1; j <= weight; j++){
				if(arr[i - 1][2] > j){
					result[i][j] = result[i - 1][j];
				}else{
					result[i][j] = (result[i - 1][j] > (result[i - 1][j - arr[i - 1][2]] + arr[i - 1][1])) ? result[i - 1][j] : result[i - 1][j - arr[i - 1][2]] + arr[i - 1][1];
				}
				
			}
		}
		
		
		return result;
	}
}
